/*
 * BinaryHeap.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi He
 *
 * Jamming is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef __BINARYHEAP_H__
#define __BINARYHEAP_H__
#include <vector>
#include <functional>
#ifdef __DEBUG__
#include <iostream>
#endif 
namespace Heap {
    template <class T,class Tcontainer = std::vector<T>,class _TypeCompare=std::less<T> >
    class BinaryHeap {
        inline int parent(int idx) {
            return ((1+idx)>>1)-1;
        };
        inline int left(int idx) {
            return ((idx+1)<<1)-1;
        };
        inline int right(int idx) {
            return ((idx+1)<<1);
        };
        inline int max(int i1, int i2) {
            if (i1<=_bottom && i2<=_bottom) return _heap[i1] > _heap[i2]? i1 :i2;
            else return i1< i2? i1: i2;
        };
        inline void swap(int i,int j) {
            T tmp=_heap[i];
            _heap[i]=_heap[j];
            _heap[j]=tmp;
        };
        inline void heapfy(int i) {
            int t;
            while( left(i) <= _bottom) {
                if (_heap[i] < _heap[t=max(left(i),right(i))]) swap(i,t);
                else return;
            }
        }
        int _bottom;
        Tcontainer _heap;
        public:
        BinaryHeap() {
            _bottom=-1;
        };
        T top() {
            return _heap[0];
        };
        void push(T value) {
            int i=++_bottom;
            int p;
            _heap[i]=value;
            while ( (p=parent(i))>=0 && _heap[i] > _heap[p]) { // i greater than p, up heap 
                swap(i,p);
                i=p;
            }
#ifdef __DEBUG__
            std::cout<<"Push "<<value<<std::endl;
            for(i=0;i<=_bottom;i++) {
                std::cout<<_heap[i]<<" ";
            }
            std::cout<<std::endl;
#endif
        }
        T pop() {
            T value=_heap[0];
            _heap[0]=_heap[_bottom--];
            int i=0;
            heapfy(i);
#ifdef __DEBUG__
            std::cout<<"Pop "<<value<<std::endl;
            for(i=0;i<=_bottom;i++) {
                std::cout<<_heap[i]<<" ";
            }
            std::cout<<std::endl;
#endif
        return value;
        };
        bool empty() {
           return _bottom<0 ? true:false;
        }
        bool append(const T* arToAppend,const int nSize) {
            for(int i=0;i<nSize;i++) push(arToAppend[i]);
        }
    };
};

#endif /* __BINARYHEAP_H__ */

